package mo.leetcode_top;

import mo.common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class L230 {

    private List<Integer> keys = new ArrayList<>();

    public int kthSmallest(TreeNode root, int k) {
        int cnt = 0;
        Stack<TreeNode> stack = new Stack<>();
        //中序遍历：左 -> 中 -> 右
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            TreeNode node = stack.pop();
            cnt++;
            if (cnt == k) {
                return node.val;
            }
            p = node.right;
        }
        return 0;
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.right = new TreeNode(4);
        root.left.right = new TreeNode(2);
        L230 test = new L230();
        System.out.println(test.kthSmallest(root, 2));
    }

}
